Exercise 7 (Homework 3).
(pumping lemma,
diagonalization,
hard exercise)
Approximations of real numbers
Given a real number r\in [0,1), let L_r \subseteq \{0,1\}^* be the language consisting of non-empty words w, where w coincides with the first |w| digits of the binary expansion of r. For instance,
- 1/2 in binary is .1, and hence L_{1/2}=\{1, 10, 100, 1000, \dots\}
- 1/3 in binary is .01010101\dots, and hence L_{1/3}=\{0, 01, 010,0101,01010, \dots\}
- Show that L_r is a regular language if and only if r is a rational number.
- Argue why for almost all real numbers r\in [0,1), L_r is not a regular language.